﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Alogrithms
{
    public class WeightedQuickUnionUF
    {
        private int[] id;    // id[i] = parent of i
        private int[] sz;    // sz[i] = number of objects in subtree rooted at i
        private int m_count;   // number of components

        private static long callFind = 0;
        private static long callUnion = 0;

        // Create an empty union find data structure with N isolated sets.
        public WeightedQuickUnionUF(int N)
        {
            m_count = N;
            id = new int[N];
            sz = new int[N];
            for (int i = 0; i < N; i++)
            {
                id[i] = i;
                sz[i] = 1;
            }
        }

        // Return the number of disjoint sets.
        public int count()
        {
            return m_count;
        }

        // Return component identifier for component containing p
        public int find(int p)
        {
            ++callFind;

            while (p != id[p])
                p = id[p];
            return p;
        }

        // Are objects p and q in the same set?
        public bool connected(int p, int q)
        {
            return find(p) == find(q);
        }


        // Replace sets containing p and q with their union.
        public void union(int p, int q)
        {
            ++callUnion;

            int i = find(p);
            int j = find(q);
            if (i == j) return;

            // make smaller root point to larger one
            if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
            else { id[j] = i; sz[i] += sz[j]; }
            m_count--;
        }


        public override string ToString()
        {
            return string.Format("union: {0}\t\tfind:{1}", callUnion, callFind);
        }

        public void Reset()
        {
            callFind = 0;
            callUnion = 0;
        }

    }
}
